<!--
 * @Author: zengwj
 * @Date: 2021-11-03 18:09:58
 * @LastEditors: zengwj
 * @LastEditTime: 2021-11-04 15:58:35
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    var findItinerary = function (tickets) {
      let path = []
      let res = []
      let len = tickets.length
      let map = new Map()
      for (let i = 0; i < tickets.length; i++) {
        let old = map.get(tickets[i][0])
        map.set(tickets[i][0], old ? [...old, tickets[i][1]] : [tickets[i][1]])
      }
      console.log(map)
      function backtrack(name) {
        if (path.length === len) {
          path.push(name)
          res.push([...path])
          return
        }
        let newName = null
        const toList = map.get(name)
        if (!toList) {
          return
        }
        toList.sort()
        for (let i = 0; i < toList.length; i++) {
          path.push(name)
          newName = toList[i]
          const newToList = [...toList]
          map[name].splice(i, 1)
          if (!map.get(newName)) continue
          backtrack(newName)
          map[name].splice(i, 0, newName)
          path.pop()
        }

      }
      backtrack('JFK')
      return res[0]
    };
    console.log(findItinerary(
      [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]));
  </script>
</body>

</html>